package three;
import java.util.*;
public class A053 {


    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("abc");
        System.out.println(set.contains("abc"));
    }

}

//模拟字典树
class Trie {

    //1.创建一个节点：每个节点存储一个字符
    private static class Node {
        boolean end;  //比如存储某一个字符串，这个字符串的最后一个节点位置代表结束节点
        Node[] son = new Node[26]; //26叉树，代表26个小写字母
    }

    private final Node root = new Node();

    public Trie() {

    }

    public void insert(String word) {
        Node cur = root;
        for(char ch : word.toCharArray()) {
            ch -= 'a';//此时ch为0-25之间的一个数字
            if(cur.son[ch]==null) {
                //这里表示该字符的节点还没有被创建出来,如果有了不需要创建
                cur.son[ch] = new Node();
            }
            //继续往下走
            cur = cur.son[ch];
        }
        cur.end = true;//关键一步，表示word到这里就结束了
    }

    private int find(String word) {
        Node cur = root;
        for(char ch : word.toCharArray()) {
            ch -= 'a';
            if(cur.son[ch] == null) { //不存在这个字符，说明字符串不匹配。
                return 0;
            }
            cur = cur.son[ch];//继续往下走
        }
        if(cur.end == true) { //完全匹配，说明到这里结束了，刚好
            return 2;
        }else {
            return 1;   //前缀匹配
        }
    }


    public boolean search(String word) {
        if(find(word)==2) return true;
        return false;
    }

    public boolean startsWith(String prefix) {
        if(find(prefix)!=0) return true;
        return false;
    }
}
